Припадност тачке многоуглу

Припаднст тачке многоуглу или полигону је проблем који се често среће у рачунарској графици, а суштина је одређивање припадности произвољне тачке површини обухваћеној датим многоуглом. Током времена развијено је више алгоритама који приступају овом проблему. Углавном се његова декларација своди на дат уређени скуп тачака, које представљју многоугао, и још једну тачку, за коју треба проверити припадност датом многоуглу.

Метода зрака

Припадност темена страницама многоугла, распоређених према индексима.

Пример проласка зрака кроз два темена, од којих прво не треба да буде рачунато јер му се и претходно и следеће теме налазе са исте стране зрака, док друго треба.

Метод зрака полази од чињенице да зрак (полуправа) при сваком пресецању границе многоугла или улази или излази из њега. Тако би при се при повлачењу зрака из дате тачке и бројањем његових пресека са тим многоуглом дало установити да ли је тачка (почетак зрака) унутар многоугла или не:

Непаран број пресека: тачка је у многоуглу
Паран број пресека: тачка је ван многоугла

Зрак може имати било који смер, али се због лакоће рачунања узимају вектори паралелни са x или y-осом.

У пракси се бројање пресека постиже посебном провером за сваку страницу многоугла. Ствар која може узроковати проблем приликом бројања је пролазак зрака кроз неко теме многоугла. И овај проблем има више аспеката. Први аспекат је чињеница да једно теме многоугла деле две странице многоугла. Други је то што пролазак кроз теме не мора да значи излазак или улазак из многоугла.

Први део проблема се решава поделом темена између страница, тако да свака страница садржи само једно теме тј. представља полузатворени интервал. Како су сва темена у многоуглу индексирана, правило би могло да додељује неко теме страници ако исто:

има највећи постојећи индекс, или
уколико има индекс мањи од индекса другог темена

Други део проблема избегава непожељне случајеве тако што не броји проласке кроз темена код којих се и претходно и следеће теме налазе са исте стране зрака. Наравно, уколико се дата тачка поклапа са неким теменом или лежи на некој страници, одмах се може закључити да припада многоуглу.

Још један подслучај вредан разматрања је када је нека од страница многоугла паралелна са смером вектора и лежи на зраку. Логички се у овом случају ништа не мења, али због природе рачуна се овај случај посебно обрађује.

Имплементација

Рецимо да је вектор зрака (0,-1) тј. вертикалан и усмерен „надоле“ односно у негативном смеру y-осе. Тада ће главна метода за ову проверу у Јави изгледати овако:

public static boolean tackaUMnogouglu(Tacka[] tacke, Tacka p) {
  int brojPreseka = 0;
  for(int i=0, j=1, k = tacke.length - 1; i < tacke.length; i++, j++, k++) {
    if(j == tacke.length) {
      j = 0;
    }
    if(k == tacke.length) {
      k = 0;
    }
    switch(tackaIznadStranice(p, tacke[i], tacke[j], tacke[k])) {
      case 1:
        brojPreseka++;
        break;
      case -1:
        return true;
    }
  }
  return (brojPreseka % 2) == 1;
}

Ова метода враћа true уколико је тачка унутар многоугла, а у супротном случају false. Помоћној методи tackaIznadStranice се увек прослеђују тачка и три темена. Прва два представљају теме које припада страници, друго теме странице које се не рачуна као њен део, и теме које претходи првом темену, да би се могло установити да ли теме треба рачуанти или не у специјалним случајевима. Метода враћа 1 уколико се тачка налази изнад странице (дакле дужи, не праве одређене овом страницом), -1 уколико се налази негде на њој, и иначе 0. Притом прати горенаведени алгоритам.

public static int tackaIznadStranice(Tacka p, Tacka a, Tacka b, Tacka c) {
  // Специјалан случај, кад је страница паралелна вектору зрака
  if(Math.abs(a.x - b.x) < 1e-4) {
    // Да ли је тачка на истој x-координати?
    if(Math.abs(p.x - a.x) < 1e-4) { 
      if((p.y >= a.y && p.y <= b.y) || (p.y >= b.y && p.y <= a.y)) {
        return -1; // Ако се још налази и на правој, вратити -1.
      }
      // Ако се налази изнад праве, рачунати као пресек
      return p.y > a.y && p.y > b.y ? 1 : 0; 
    }
    return 0; // Иначе, нема пресека
  }

  // Ако тачка лежи на x-координати темена
  if(Math.abs(a.x - p.x) < 1e-4) {
    if(Math.abs(a.y - p.y) < 1e-4) { // Ако је тачка заправо у темену
      return -1;
    }
    if(p.y > a.y) { // Ако је тачка изнад темена
      // И ако теме треба да се урачуна, вратити један пресек
      return ((p.x - b.x)*(p.x - c.x) < 0) ?  1 : 0;
    }
  }

  // Ако тачка није изнад, на или испод странице, вратити 0
  if((p.x < a.x || p.x >= b.x) && (p.x > a.x || p.x <= b.x)) {
    return 0;
  }

  // y-координата дужи на пресеку са правом кроз тачку p у смеру зрака
  double hab = a.y + (b.y - a.y) * (p.x - a.x) / (b.x - a.x);

  // Ако је тачка на правој, вратити -1
  if(Math.abs(hab - p.y) < 1e-4) {
    return -1;
  }

  // Ако је тачка изнад, вратити 1. У супротном 0.
  return hab < p.y ? 1 : 0;
}

Метода индекса тачке

Други метод је одређивање индекса дате тачке P у односу на дату путању. Ова путања може бити одређена страницама многоугла, али и било којом затвореном кривом. На путањи се изабире произвољна полазна тачка, и произвољним смером кретања се обилази цела путања до повратка у полазну тачку. При томе дата тачка P прати ово кретање ротирајући у месту, око саме себе. Број пуних обртаја које тачка P овако направи се назива њеним индексом у односу на дату путању. Овај број припада скупу N₀, а тачка P се налази унутар дате путање (односно фигуре коју она образује) уколико је овај број већи од нуле.

Метода суме површина

Припадност тачке многоуглу се може одредити и сумом површина свих троуглова које она гради са страницама датог многоугла. Уколико је ова сума једнака површини многоугла, тачка се налази унутар њега. Уколико је сума површина ових троуглова већа од површине многоугла, онда се налази ван њега. Ограничење ове методе је што се може применити само на конвексне многоуглове.

Ова метода би се такође могла сматрати најнепрецизнијом од две претходне, јер се при сваком рачуању површине троугла због особина бројева у покретном зарезу прави грешка која се акумулира са порастом броја страница многоугла.

Имплементација

Према формули којом се на основу координата тачака може израчуати површина многоугла, може се одредити површина како задатог многоугла, тако и сваког троугла на кога је подељен. Ова метода би у Јави изгледала овако:

public static double povrsina(Tacka... tacke) {
 double pov = 0;
  for(int i=0, j=1; i<tacke.length; i++, j++) {
    if(j == tacke.length) {
      j = 0;
    }
    pov += tacke[i].x * tacke[j].y - tacke[i].y * tacke[j].x;
  }
  return Math.abs(pov) / 2;
}

А метода која одређује припадност тачке многоуглу, би се свела на:

public static boolean tackaUMnogouglu(Tacka[] tacke, Tacka p) {
  double povrsinaMnogougla = povrsina(tacke);
  double sumaPovrsina = 0;
  for(int i=0, j=1; i < tacke.length; i++, j++) {
    if(j == tacke.length) {
      j = 0;
    }
    sumaPovrsina += povrsina(tacke[i], tacke[j], p);
  }
  return Math.abs(sumaPovrsina - povrsinaMnogougla) < 1e-4;
}